// 数组intervals表示若干个区间的集合，请合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需要恰好原数组的所有区间

// 思路，先按左端点排序，让左端点有序，遍历元素，当前元素的左端点和上一个元素的右端点比较，如果大于，则push数组，否则则更新上一个元素的右端点
// 时间复杂度：O(nlogn)
// 空间复杂度：O(logn)

function merge(arr) {
    arr.sort((a, b) => a[0] - b[0])
    let ans = [arr[0]]
    console.log(arr)
    for (let i = 1; i < arr.length; i++) {
        if (arr[i][0] > ans[ans.length - 1][1]) {
            ans.push(arr[i])
        } else {
            ans[ans.length - 1][1] = Math.max(ans[ans.length - 1][1], arr[i][1])
        }
    }
    return ans
}

let intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
intervals = [[1,4],[0,2],[3,5]]
console.log(merge(intervals))